Many current data processing algorithms, such as entropy coding, repeatedly use large look up tables with the values included in these tables determined at run time. Entropy coding is a data compression technique that employs fewer coded bits for more frequently used symbols than for less frequently used symbols. In the prior art the complete index for the look up table element was calculated before the memory access to the look up table. Current data processors have long latencies for memory access relative to the data processor operation even for accesses that hit into a cache. This long memory access latency worsens the performance for algorithms that are lookup table intensive.
In many cases the desired look up table entry is defined by a coarse index that can be quickly determined and a fine index indicating an offset from the coarse index. This occurs because the entropy statistics define an inherently jagged table. In such a jagged table the coarse index would be the base pointer to a sub-table. The fine index selects the entry in this sub-table. In many cases this sub-table is small and typically includes less than 16 bytes of data.